package com.zlk.algorithm.algorithm.dynamicPlan.threeDimension;

import java.util.Stack;

// 一和零(多维费用背包)
// 给你一个二进制字符串数组 strs 和两个整数 m 和 n
// 请你找出并返回 strs 的最大子集的长度
// 该子集中 最多 有 m 个 0 和 n 个 1
// 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集
// 测试链接 : https://leetcode.cn/problems/ones-and-zeroes/
public class Code01_OnesAndZeroes {

    public int findMaxForm(String[] strs, int m, int n) {
        //return f1(strs,0,m,n,0,0);
//        int[][][] dp = new int[strs.length+1][m+1][n+1];
//        for (int i = 0; i < strs.length; i++) {
//            for (int z = 0; z <= m; z++) {
//                for (int o = 0; o <= n; o++) {
//                    dp[i][z][o] = -1;
//                }
//            }
//        }
//        return f2(strs,0,m,n,0,0,dp);
        return f4(strs, m, n);
    }

    public static void main(String[] args) {
        Code01_OnesAndZeroes test = new Code01_OnesAndZeroes();
        String[] strings = new String[]{"10","0001","111001","1","0"};
        System.out.println(test.f4(strings, 5, 3));
    }


    /**
     * 严格位置动态规划
     * 空间压缩 +枚举优化
     * @param strs
     * @param m
     * @param n
     * @return
     */
    private int f5(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (int i = strs.length-1; i >=0 ; i--) {
            String str = strs[i];
            int mcount = 0;
            int ncount = 0;
            for (char c : str.toCharArray()) {
                if (c == '0') {
                    mcount++;
                } else {
                    ncount++;
                }
            }
            for (int y = 0; y <= m-mcount; y++) {
                for (int z = 0; z <=n-ncount ; z++) {
                    if (ncount + z <= n && mcount + y <= m) {
                        //ans = Math.max(ans, 1 + f2(strs, i + 1, m, n, loadm + mcount, loadn + ncount, dp));
                        dp[y][z] =Math.max(dp[y][z],1+dp[mcount+y][ncount+z]);
                    }
                }
            }
        }
        return dp[0][0];
    }

    /**
     * 严格位置动态规划
     * 空间压缩
     * @param strs
     * @param m
     * @param n
     * @return
     */
    private int f4(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (int i = strs.length-1; i >=0 ; i--) {
            String str = strs[i];
            int mcount = 0;
            int ncount = 0;
            for (char c : str.toCharArray()) {
                if (c == '0') {
                    mcount++;
                } else {
                    ncount++;
                }
            }
            for (int y = 0; y <= m; y++) {
                for (int z = 0; z <=n ; z++) {
                    //不要
                    int ans = dp[y][z];    ;//  f2(strs, i + 1, m, n, loadm, loadn, dp);
                    //要
                    if (ncount + z <= n && mcount + y <= m) {
                        //ans = Math.max(ans, 1 + f2(strs, i + 1, m, n, loadm + mcount, loadn + ncount, dp));
                        ans =Math.max(ans,1+dp[mcount+y][ncount+z]);
                    }
                    dp[y][z] = ans;
                }
            }
        }
        return dp[0][0];
    }

    /**
     * 严格位置动态规划
     *
     * @param strs
     * @param m
     * @param n
     * @return
     */
    private int f3(String[] strs, int m, int n) {
        int[][][] dp = new int[strs.length + 1][m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                dp[strs.length][i][j] = 0;
            }
        }
        for (int i = strs.length-1; i >=0 ; i--) {
            String str = strs[i];
            int mcount = 0;
            int ncount = 0;
            for (char c : str.toCharArray()) {
                if (c == '0') {
                    mcount++;
                } else {
                    ncount++;
                }
            }
            for (int y = m; y >=0 ; y--) {
                for (int z = n; z >=0 ; z--) {
                    //不要
                    int ans = dp[i+1][y][z];    ;//  f2(strs, i + 1, m, n, loadm, loadn, dp);
                    //要
                    if (ncount + z <= n && mcount + y <= m) {
                        //ans = Math.max(ans, 1 + f2(strs, i + 1, m, n, loadm + mcount, loadn + ncount, dp));
                        ans =Math.max(ans,1+dp[i+1][mcount+y][ncount+z]);
                    }
                    dp[i][y][z] = ans;
                }
            }
        }
        return dp[0][0][0];
    }

    private int f2(String[] strs, int i, int m, int n, int loadm, int loadn, int[][][] dp) {
        if (i == strs.length) {
            dp[i][loadm][loadn] = 0;
            return 0;
        }
        if (dp[i][loadm][loadn] != -1) {
            return dp[i][loadm][loadn];
        }
        String str = strs[i];
        int mcount = 0;
        int ncount = 0;
        for (char c : str.toCharArray()) {
            if (c == '0') {
                mcount++;
            } else {
                ncount++;
            }
        }
        //不要
        int ans = f2(strs, i + 1, m, n, loadm, loadn, dp);
        //要
        if (ncount + loadn <= n && mcount + loadm <= m) {
            ans = Math.max(ans, 1 + f2(strs, i + 1, m, n, loadm + mcount, loadn + ncount, dp));
        }
        dp[i][loadm][loadn] = ans;
        return ans;
    }

    /**
     *
     * @param strs
     * @param i  前i位置字符
     * @param m
     * @param n
     * @param loadm  装载的m的长度
     * @param loadn  状态的n的长度
     * @return
     */
    private int f1(String[] strs, int i, int m, int n, int loadm, int loadn) {
        if (i == strs.length) {
            return 0;
        }
        String str = strs[i];
        int mcount = 0;
        int ncount = 0;
        for (char c : str.toCharArray()) {
            if (c == '0') {
                mcount++;
            } else {
                ncount++;
            }
        }
        //不要
        int ans = f1(strs, i + 1, m, n, loadm, loadn);
        //要
        if (ncount + loadn <= n && mcount + loadm <= m) {
            ans = Math.max(ans, 1 + f1(strs, i + 1, m, n, loadm + mcount, loadn + ncount));
        }
        return ans;
    }
}
